; SICP, 2.60
;
; We specified that a set would be represented as a list with no duplicates.
; Now suppose we allow duplicates. For instance, the set {1,2,3} could be
; represented as the list (2 3 2 1 3 2 2).
;
; Design procedures element-of-set?, adjoin-set, union-set, and intersection-set
; that operate on this representation. How does the efficiency of each compare
; with the corresponding procedure for the non-duplicate representation? Are
; there applications for which you would use this representation in preference
; to the non-duplicate one?

; Performance:
; In this "duplicates OK" version, all operations except adjoin-set are slower.

(define nil '())

; element-of-set? keeps unchanged.

; note that cons is prefered to append for performance.
(define (adjoin-set x set)
  (cons x set))

; union-set can keep unchanged or be changed not to call element-of-set?.
(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        (else
          (cons (car set1)
                (union-set (cdr set1) set2)))))

; intersection-set keeps unchanged.
; but note that after intersection there still might be duplicates.

